package Salesman;

import Salesman.Data.DataProvider;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public class TSPInsertion extends TSPEngine {

    Distances dist = DataProvider.getDistances();
    CityLink steps;
    BitSet freeCities;
    BitSet usedCities;

    @Override
    public void start(City city) {
        dist = DataProvider.getDistances();
        int cityCount = DataProvider.getCityData().size();
        freeCities = new BitSet(cityCount);
        usedCities = new BitSet(cityCount);
        for (int i = 0; i < cityCount; i++) {
            if (DataProvider.getCityData().get(i).isInSimulation()) {
                freeCities.set(i);
            }
        }

        int i = DataProvider.getCityData().indexOf(city);
        freeCities.clear(i);
        usedCities.set(i);
        steps = new CityLink(i);
        steps.link(new CityLink(i));
    }

    @Override
    public boolean next() {
        if (freeCities.isEmpty()) {
            return false;
        }

        double w = 0;
        CityLink cl = null;
        for (int i = freeCities.nextSetBit(0); i >= 0; i = freeCities.nextSetBit(i + 1)) {
            for (int j = usedCities.nextSetBit(0); j >= 0; j = usedCities.nextSetBit(j + 1)) {
                double d = dist.get(i, j);
                if (w < d) {
                    w = d;
                    cl = new CityLink(i);
                }
            }
        }

        w = Double.POSITIVE_INFINITY;
        CityLink in = null;
        CityLink c = steps;
        while (c.next() != null) {
            double d = weight(c.index(), c.next().index(), cl.index());
            if (w > d) {
                w = d;
                in = c;
            }
            c = c.next();
        }

        in.insert(cl);
        freeCities.clear(cl.index());
        usedCities.set(cl.index());
        fireListener(new Step(steps));
        return true;
    }

    private double weight(int a, int b, int c) {
        double ab = dist.get(a, b);
        double cb = dist.get(c, b);
        double ac = dist.get(a, c);

        if (ab > Double.MAX_VALUE) {
            return ac + cb;
        } else {
            return ac + cb - ab;
        }
    }

    @Override
    public String toString() {
        return "Insertion Heuristik";


    }
}

class Step extends AbstractStep {

    List<City> list = new ArrayList<City>();

    public Step(CityLink cities) {
        while (cities != null) {
            list.add(DataProvider.getCityData().get(cities.index()));
            cities = cities.next();
        }
    }

    @Override
    public List<City> getCities() {
        return list;
    }

    @Override
    public String toString() {
        List<City> l = getCities();
        double complete = 0, step = 0;

        for (int i = 0; i < (l.size() - 1); i++) {
            step = DataProvider.getDistances().get(
                    DataProvider.getCityData().indexOf(l.get(i)),
                    DataProvider.getCityData().indexOf(l.get(i + 1)));
            complete += step;
        }

        DecimalFormat f = new DecimalFormat("0.#");
        return "Route: " + routeToString() + "\n"
                + "Gesamtweg: " + f.format(complete) + " km\n\n";
    }
}

class CityLink {

    private int cityIndex;
    private CityLink next;

    public CityLink(int cityIndex) {
        this.cityIndex = cityIndex;
    }

    public int index() {
        return cityIndex;
    }

    public void link(CityLink next) {
        this.next = next;
    }

    public CityLink next() {
        return next;
    }

    public void insert(CityLink element) {
        element.link(next);
        link(element);
    }
}